package daily_exercise;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Demo9 {


    public long beautifulSubarrays(int[] nums) {
        // 核心思路：区间 i~j 所有整数异或结果为 0
        int n = nums.length;
        // Key：区间0~i的整数异或结果   Value：个数
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0, 1); // 第一个数可能为 0
        int prev = 0;   // 记录以下标 i-1 为结尾的数组，异或的结果
        long res = 0;
        for (int i = 0; i < n; i++) {
            int tmp = prev ^ nums[i];
            res += hash.getOrDefault(tmp, 0);
            hash.put(tmp, hash.getOrDefault(tmp, 0) + 1);
            prev = tmp;
        }
        return res;
    }


    //  2597. 美丽子集的数目
    class Solution {
        private int n, res;
        private int[] path;
        private int count;  // 记录path中有多少个元素
        private int[] nums;

        public int beautifulSubsets(int[] nums, int k) {
            n = nums.length;
            this.nums = nums;
            path = new int[2001];
            dfs(0, k);
            return res;
        }
        private void dfs(int cur, int k) {
            if (cur == n) {
                if (count > 0) res++;
                return;
            }

            // 选或不选
            // 1. 看是否可选
            int curNum = nums[cur];
            int num1 = k + curNum, num2 = curNum - k;
            if ((num1 <= 0 || path[num1] == 0) && (num2 <= 0 || path[num2] == 0)) {
                path[curNum]++;
                count++;
                dfs(cur + 1, k);
                path[curNum]--;
                count--;
            }
            // 2.不选
            dfs(cur + 1, k);
        }
    }




    // 3305. 元音辅音字符串计数 I
    public int countOfSubstrings(String word, int k) {
        int n = word.length();
        if (n < 5) return 0;

        String str = "aeiou";
        char[] arr = word.toCharArray();
        // calc[i]: 从下标 i 开始，后面有多少个连续的元音字母
        int[] calc = new int[n + 1];
        for (int i = n - 2; i >= 0; i--) {
            char ch = arr[i + 1];
            if (str.contains("" + ch)) {
                calc[i] = calc[i + 1] + 1;
            }
        }

        int[] flag = new int[26];       // 记录每个字符出现的次数
        int left = 0, right = 0;
        int count1 = 0;     // 记录包含的元音字母种类数
        int count2 = 0;     // 记录包括的辅音字母总数
        int res = 0;
        while (right < n) {
            char ch = arr[right];
            // 进窗口
            if (str.contains("" + ch)) {
                if (flag[ch - 'a']++ == 0) {
                    count1++;
                }
            } else {
                count2++;
            }

            while (count1 == 5 && count2 >= k) {
                // 统计次数
                if (count2 == k) {
                    res++;
                    // 从下标 right 开始，后面有多少个连续的元音字母都统计进结果
                    if (right < n - 1 && str.contains("" + arr[right + 1])) {
                        res += calc[right];
                    }
                }
                // 出窗口
                char tmp = arr[left++];
                if (str.contains("" + tmp)) {
                    if(--flag[tmp - 'a'] == 0) {
                        count1--;
                    }
                } else {
                    count2--;
                }
            }
            right++;
        }
        return res;
    }


    // 3306. 元音辅音字符串计数 II
    public long countOfSubstrings2(String word, int k) {
        char[] arr = word.toCharArray();
        int len = word.length();
        if (len < 5) {
            return 0;
        }

        int[] flag = new int[len + 1];    // flag[i]:下标 i 后面有多少个连续的元音字母
        for (int i = len - 2; i >= 0; i--) {
            char ch = arr[i + 1];
            if (check(ch)) {
                flag[i] = flag[i + 1] + 1;
            }
        }

        int left = 0, right = 0;
        int[] hash = new int[26];   // 统计元音字母出现的次数
        int count1 = 0;             // 统计元音字母出现的种类数
        int count2 = 0;             // 统计辅音字母出现的个数
        long res = 0;
        while (right < len) {
            // 入窗口
            char ch = arr[right];
            if (check(ch)) {
                if (hash[ch - 'a']++ == 0) {
                    count1++;
                }
            } else {
                count2++;
            }

            while (count1 == 5 && count2 >= k) {
                // 统计次数
                if (count2 == k) {
                    res++;
                    // 从下标 right 开始，后面有多少个连续的元音字母都统计进结果
                    if (right < len - 1 && check(arr[right + 1])) {
                        res += flag[right];
                    }
                }
                // 出窗口
                char tmp = arr[left++];
                if (check(tmp)) {
                    if(--hash[tmp - 'a'] == 0) {
                        count1--;
                    }
                } else {
                    count2--;
                }
            }
            right++;
        }
        return res;
    }
    private boolean check(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }


    // 3340. 检查平衡字符串
    public boolean isBalanced(String num) {
        int oddSum = 0, evenSum = 0;
        for (int i = 0, n = num.length(); i < n; i++) {
            int tmp = num.charAt(i) - '0';
            if (i % 2 == 0) {
                evenSum += tmp;
            } else {
                oddSum += tmp;
            }
        }
        return oddSum == evenSum;
    }


    // 3110. 字符串的分数
    public int scoreOfString(String s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n - 1; i++) {
            res += Math.abs(s.charAt(i) - s.charAt(i + 1));
        }
        return res;
    }



    // 2643. 一最多的行
    public int[] rowAndMaximumOnes(int[][] mat) {
        int[] res = new int[2];
        int n = mat.length, m = mat[0].length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 1) count++;
            }
            if (count > res[1]) {
                res[0] = i;
                res[1] = count;
            }
            if (count == m) return res;
        }
        return res;
    }


    //  1094. 拼车(差分数组)
    public boolean carPooling(int[][] trips, int capacity) {
        // 利用差分数组
        int[] diff = new int[1001];
        for (int[] t : trips) {
            int num = t[0], from = t[1], to = t[2];
            diff[from] += num;
            // 在 to 的时候就已经下车了，[from, to]是一个左闭右开的区间
            diff[to] -= num;
        }

        int count = 0;
        for (int x : diff) {
            count += x;
            if (count > capacity) return false;
        }
        return true;
    }


    // 3355. 零数组变换 I(差分数组)
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] diff = new int[n + 1];
        for (int[] q : queries) {
            // 统计的是区间 -1
            diff[q[0]]--;
            diff[q[1] + 1]++;
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            count += diff[i];
            if (nums[i] + count > 0) {
                return false;
            }
        }
        return true;
    }

}
